class List {
	/*
	 * Zu Aufgabe e) Verwendet man das Interface Iterator, muss man Methoden implementieren.
	 * Durch diese wird es möglich z.b. mit Hilfe einer foreach-Schleife über jedes Element in der Liste
	 * zu Iterieren.
	 */
	
	
	private ListNode head, tail;
	private int size;

	public List() {

		head = tail = null;
		size = 0;
	}

	/**
	 * Fügt ein Element am Ende der Liste an. 
	 * 
	 * 
	 * Die Laufzeit ist hier sehr viel geringer als bei der Vektor/Array Methode.
	 * Hier muss kein Array vergrößert werden, es wird einfach ein neues Objekt vom Typ
	 * ListNode erzeugt und an das Ende der Liste gehängt. Die Laufzeit bleibt auch bei großen
	 * Listen immer gleich.
	 * 
	 * Generell bleibt die Laufzeit bei allen Mothoden der Liste konstant.
	 * @param obj Das einzufügende Element.
	 */
	public void add(Object obj) {

		if (size == 0) {
			head = tail = (ListNode) obj;
			size++;
		} else {
			ListNode tmp = (ListNode) obj;
			tail.next = tmp;
			tail = tmp;
			size++;
		}
	}
	
	/**
	 * Gibt das i-te Element zurück.
	 * @param i Der Index des Elements
	 * @return Das Element
	 */
	public Object get(int i)
	{
		if(i > size - 1) return null;
		
		ListNode temp = head;
		for (int j = 0; j < i; j++) 
			temp = temp.next;
		
		return temp;
	}

	/**
	 * Entfernt das i-te Element und gibt es zurück.
	 * 
	 * Die Laufzeit ist immer die selbe, da nur zwei Zeiger auf ein anderes Ziel eingestellt werden müssen.
	 * @param i Der Index, an dem das Element entfernt werden soll.
	 * @return Das entfernte Element.
	 */
	public Object remove(int i)
	{
		if (i > size - 1) return null;
		
		ListNode temp = head;
		for (int j = 0; j < i - 1; j++) 
			temp = temp.next;
		
		ListNode tempRemove = temp.next;
		temp.next = temp.next.next;
		
		size--;
		return tempRemove;
		
	}

	/**
	 * Gibt Auskunft, ob das übergebene Objekt bereits gespeichert ist.
	 * 
	 * Bei der contains Methode besteht das Problem, das zwei Objekte miteinander Verglichen werden.
	 * Allerdings sind diese nur dann gleich wenn sie auf das selbe Objekt zeigen. Also deren Werte 
	 * spielen bei der gleichheit keine Rolle. D.h. das ein Objekt vom Typ ListNode mit den selben Eigenschaften
	 * eines Objektes, dass in dem Array enthalten ist, wird dennoch als ein anderes angesehen.
	 * @param obj Das Element, das geprüft werden soll.
	 * @return
	 */
	public boolean contains(Object obj)
	{
		ListNode temp = head;
		if (temp == obj) return true;
		for (int i = 0; i < size - 1; i++)
		{
			temp = temp.next;
			if (temp == obj) return true;
		}
		
		return false;
	}
	
	/**
	 * Fügt obj an Position i ein. Die Elemente hinter der Position werden weiter nach hinten verschoben.
	 * @param obj Das Element, dass eingesetzt werden soll.
	 * @param i
	 */
	public void insert(Object obj , int i)
	{
		if(i > size - 1) this.add(obj);
		
		else if (i == 0) 
		{	
			ListNode temp = head;
			
			head = (ListNode) obj;
			head.next = temp;
			size++;
		}
		
		else
		{
			ListNode temp = head;
			for (int j = 0; j <= i; j++) 
				temp = temp.next;
			
			((ListNode) obj).next = temp;
			
			 temp = head;	
			 for (int j = 0; j < i; j++) 
				temp = temp.next;
			 
			 temp.next = (ListNode) obj;
		}
	}

	/**
	 * Gibt die Größe der Liste zurück.
	 * @return
	 */
	public int size() {

		return size;
	}
}
